import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-11-09
 * Time: 21:00
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Day16 {
    //138.复制带随机指针的链表 - 标记
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            hashMap.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).random = hashMap.get(cur.random);
            cur = cur.next;
        }
        return hashMap.get(head);
    }
    //20.括号匹配问题 - 标记
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()){
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        return stack.isEmpty();
    }
    //589.N叉树的前序遍历
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        
    }
    public static void main(String[] args) {

    }
}
